home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1993 July / InfoMagic USENET CD-ROM July 1993.ISO / sources / std_unix / archive / text0027.txt < prev    next >
Encoding:
Text File  |  1993-07-06  |  5.1 KB  |  115 lines
  1. Submitted-by: dave@88open.org (Dave Cline)
  2.  
  3. [ A surprise!  An article that actually mentions a standard or two! -- mod ]
  4.  
  5. >In article <1ovqhcINNseh@ftp.UU.NET>
  6. >             jeffrey@netcom.com (Jeffrey Kegler) writes:
  7.  
  8. Note to Jeffrey: IMO, your repeated ad hominem attacks are
  9. unprofessional.
  10.  
  11. [ And no more will be tolerated by me.  I will shamelessy use my
  12.   editorial ability to remove them, if necessary.  Anything Dave
  13.   and Jeffrey have to say about each other they can say in private
  14.   from now on.  Both parties, and third parties, have expressed
  15.   unhappiness at the way the discussion has gone, and I apologise
  16.   heartily for that.  My only excuse is that I have been replacing
  17.   my computer system, and was somewhat distracted.  I will try not
  18.   to let it happen again -- mod ]
  19.  
  20. >The readership of comp.std.unix should be able to spot the above
  21. >reading of the standard as wrong with no trouble.  As a reading of ANSI
  22. >X3.159-1989, section 2.2.4.2.1 shows, INT_MAX is a *minimum* -- the
  23. >standard gives a magnitude they must be at least as large as, but
  24. >implementors may define their magnitudes larger.
  25.  
  26. Sure, an *implementation* is free to extend the range of
  27. integers beyond the minimum guaranteed INT_MAX value.  That's a
  28. given.  However, the context of this discussion is test method
  29. standards and test suites for various Unix standards (not just
  30. the misapplication of Turing machine models).  The rules are
  31. obviously a bit different for test suites, (or at least it seems
  32. to me that it should have been obvious). 
  33.  
  34. A test method implementation that blindly stores a value greater
  35. than the minimum guaranteed value of INT_MAX into an int is
  36. incorrect, or at least not strictly conforming according to the
  37. ANSI C and POSIX.1 rules.  A standard conforming C compilation
  38. system could (quite properly) reject such a test implementation
  39. if the implementation supported only a 16 bit ints.  If the
  40. conformance test suite isn't portable, it isn't a valid test of
  41. system conformance.  So while INT_MAX may not constrain an
  42. implementation, it does constrain a test suite. 
  43.  
  44. >sizeof(char *) is
  45. >implementation defined, pure and simple (3.3.3.4, 3.3.4, F.3.7).
  46.  
  47. Agreed, sizeof(char *) is implementation defined.  But it must be
  48. finite. 
  49.  
  50. The reasoning is as follows: a conforming compilation system
  51. must accept all strictly conforming programs (X3.159-1989
  52. section 1.7).  A strictly conforming program that computes (at
  53. runtime) the usual idiom for the number of elements in an array
  54. of character pointers (sizeof(x)/sizeof(x[0])) would fail if 
  55. sizeof(char *) was unbounded because +infinity/+infinity makes
  56. no arithmetic sense.  OK? 
  57.  
  58. >But suppose it were right.  Is a memory which can consist of an
  59. >infinite number of finite words, infinite in extent, or finite?
  60. >Mathematics and intuition agree here, that an infinite number of 32 bit
  61. >words contains an infinite number of bits.
  62.  
  63. As noted above, this model violates ANSI C because it would lead
  64. to an infinite sizeof(char *) which breaks at least one strictly
  65. conforming program (all bytes must be addressible). 
  66.  
  67. The reverse, a model with a finite number of containers, each
  68. of which can store an arbitrarily large integer, also violates
  69. ANSI C. The reasoning goes as follows: sizeof(x) gives the
  70. number of bytes in x and must be finite (see above).  It is
  71. required that each byte of an object be uniquely addressable
  72. (1.6 def'n of byte).  Of necessity, one must then define the
  73. byte as the arbitrarily sized container.  The definition of byte
  74. in ANSI C (1.6) refers to a low order bit and a high order bit. 
  75. Hence, a byte is a bounded and finite quantity.  This leads to a
  76. contradiction. 
  77.  
  78. As further evidence of the ANSI C requirement for finite
  79. containers, I could cite the definition of integral types in
  80. 3.1.2.5, the rules for integral promotion, the rationale, etc. 
  81. It's really moot.  The point is that Jeffrey's Turing model
  82. doesn't match the real world of machines and standards. 
  83.  
  84. Bottom line
  85. -----------
  86.  
  87. The ANSI C memory model requires a finite number of finite-sized
  88. containers.  By extension, the POSIX.1 memory model has the same
  89. requirements.  Turing undecidability results require an infinite
  90. state space.  There is no undecidability in a finite state space.
  91. Proofs to the contrary will be welcomed in comp.theory.
  92.  
  93. This corresponds quite closely to everyone's (well, almost
  94. everyone's) intuition.  The real world does not accept Jeffrey's
  95. undecidability argument.  If he were correct, test suites for
  96. most standards would be compromised by these undecidability
  97. issues.  In practice, they don't arise. 
  98.  
  99. Here's a challenge to Jeffrey: give an example from POSIX.1
  100. where his Turing model undecidability would invalidate an
  101. otherwise legitimate assertion.
  102.  
  103. --
  104. Dave Cline                                  dave@88open.org
  105. Spring Valley Software
  106.  
  107. [ Note the reference to comp.theory.  Note the previous comments by
  108.   me, your moderator.  Note that anyone who tries my patience will
  109.   not get any truffles the next time I bring them to UseNIX 8-).
  110.   Above all, please note that this is not alt.flame, and my apologies
  111.   for not being up to snuff recently -- mod ]
  112.  
  113. Volume-Number: Volume 31, Number 30
  114.  
  115.